// 77.组合/中等/不重复组合dfs递归剪枝]
// https://leetcode.cn/problems/combinations/
// [中等]给定两个整数 n 和 k，返回范围 [1, n] 中
//所有可能的 k个数的组合，可以按任何顺序返回答案
// next permutation 输入：n = 4, k = 2 输出：
// [
//   [2,4],
//   [3,4],
//   [2,3],
//   [1,2],
//   [1,3],
//   [1,4],
// ]
// 递归：
// 1. 个数满足保存一组
// 2. 组进一个
// 3. 遍历余下每一个
#include <algorithm>
#include <iostream>
#include <map>
#include <memory>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif
// n = 4, k = 3
// s   e
// 2
class Solution {
  vector<vector<int>> answer;
  // [1-n],k个数字
  void dfs(int n, int k, int start, vector<int>& path) {
    if (path.size() == k) {
      answer.push_back(path);
      return;
    }
    // 剪枝
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
      path.push_back(i);
      dfs(n, k, i + 1, path);
      path.pop_back();
    }
  }

 public:
  vector<vector<int>> combine(int n, int k) {
    if (k <= 0 || n < k) {
      return answer;
    }
    vector<int> path;
    dfs(n, k, 1, path);
    return answer;
  }
};
int main() {
  int k = 2;
  Solution sol;
  vector<vector<int>> answer = sol.combine(4, k);
  for (auto it : answer) {
    printf("%d,%d\n", it[0], it[1]);
  }
  printf("\n");
  return 0;
}